//Winter is coming! During the contest, your first job is to design a standard 
//heater with a fixed warm radius to warm all the houses. 
//
// Every house can be warmed, as long as the house is within the heater's warm 
//radius range. 
//
// Given the positions of houses and heaters on a horizontal line, return the 
//minimum radius standard of heaters so that those heaters could cover all houses. 
//
// Notice that all the heaters follow your radius standard, and the warm radius 
//will the same. 
//
// 
// Example 1: 
//
// 
//Input: houses = [1,2,3], heaters = [2]
//Output: 1
//Explanation: The only heater was placed in the position 2, and if we use the 
//radius 1 standard, then all the houses can be warmed.
// 
//
// Example 2: 
//
// 
//Input: houses = [1,2,3,4], heaters = [1,4]
//Output: 1
//Explanation: The two heater was placed in the position 1 and 4. We need to 
//use radius 1 standard, then all the houses can be warmed.
// 
//
// Example 3: 
//
// 
//Input: houses = [1,5], heaters = [2]
//Output: 3
// 
//
// 
// Constraints: 
//
// 
// 1 <= houses.length, heaters.length <= 3 * 10⁴ 
// 1 <= houses[i], heaters[i] <= 10⁹ 
// 
//
// Related Topics 数组 双指针 二分查找 排序 👍 459 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

class P475Heaters {
    public static void main(String[] args) {

        Solution solution = new P475Heaters().new Solution();
        // TO TEST
        int[] a = new int[45];
        int[] b = new int[45];
        System.out.println(solution.findRadius(a, b));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            int houseIndex = 0;
            int heaterIndex = 0;
            int max = Integer.MIN_VALUE;
            Arrays.sort(houses);
            Arrays.sort(heaters);
            while (houseIndex < houses.length) {
                int radius = Math.abs(houses[houseIndex] - heaters[heaterIndex]);
                if (heaterIndex + 1 < heaters.length) {
                    if (radius <= Math.abs(houses[houseIndex] - heaters[heaterIndex + 1])) {
                        max = Math.max(radius, max);
                        houseIndex++;
                    } else {
                        heaterIndex++;
                    }
                } else {
                    max = Math.max(radius, max);
                    houseIndex++;
                }

            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}